package algorithm.t202111;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/30 9:50
 * @description :4道
 * 22岁的第二天，也是2021年11月的最后一天，今天获得了第一个力扣月打卡徽章，一会去跑个13公里，让11月的keep跑量到100。唉，明天就是12月，大四上半学期也要结束了
，我每天都在感叹时间流逝，也不知道到底有没有利用好每一天，就好比贪心算法（Greed Algorithm)中的思想一样：它总是做到局部最优选择，寄希望于这样的选择导致全局最优解，
意思就是，每一天都做到最好，希望最终能得到最好的结果。 努力，奋斗。
persevere to last
 2021.11.30
 李红磊
 2021年11月30日19:23:29
 */
public class t20211130 {

    //141.环形链表 快慢指针
    public boolean hasCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }
        return false;
    }

    //203.移除链表元素
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return head;
        ListNode dummy = new ListNode(-1);
        ListNode temp = dummy;
        while (temp.next != null) {
            if (temp.next.val == val) temp.next = temp.next.next;
            else temp = temp.next;
        }
        return dummy.next;
    }

    //1014.最佳观光组合
    public int maxScoreSightseeingPair(int[] values) {
        if (values == null || values.length < 2) return 0;
        int mx = values[0] + 0, ans = 0;
        for (int i = 1; i < values.length; i++) {
            ans = Math.max(values[i] - i + mx, ans);
            //更新mx
            mx = Math.max(mx, values[i] + i);
        }
        return ans;
    }

    //122.买卖股票的最佳时机2
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) return 0;
        int ans = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) ans += prices[i] - prices[i - 1];
        }

        return ans;
    }


    public static void main(String[] args) {
        int n = 188;


        int digit = 1; // 数位（个位/十位/百位/...，就是1/2/3/...）
        long start = 1; // 属于该数位的所有数的起始点数（个位是1，十位是10，百位是100）
        long index_count = digit * 9 * start; // 该数位的数一共的索引个数（不是数字个数）

        while (n > index_count) {
            // 找出 n 属于那个数位里的索引
            n -= index_count;
            ++digit;
            start *= 10;
            index_count = digit * 9 * start;
        }

        System.out.println("位数是" + digit);
    }
}
